# -*- coding:utf-8 -*-
import collections;

# 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
# 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

# 示例 1：
# 输入：s = "ADOBECODEBANC", t = "ABC"
# 输出："BANC"

# 示例 2：
# 输入：s = "a", t = "a"
# 输出："a"

# 提示：
# 1 <= s.length, t.length <= 105
# s 和 t 由英文字母组成

# 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

# 参考 0030_与所有单词相关联的字串 设计的解决方案
# 思路：
# 使用t来统计所有的元素
# 然后统计每一个符号的位置
# 按照位置向前前进已推测出结果
# eg:
# "ADOBECODEBANC", "ABC"
# A = {0, 10}
# B = {3, 9}
# C = {5, 12}
# 因为下标是按照顺序增长的，因而可能会出现以下结果
# {0, 3, 5}
# {0, 5, 9}
# {5, 9, 10}
# {9, 10, 12}

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        need = {}
        for k in t:
            need[k] = need.get(k, 0) + 1
        
        cur_need = {}
        length = 0
        begin = -1
        ret = ""
        for i in xrange(len(s)):
            k = s[i]
            if not need.has_key(k):
                continue
            
            if begin == -1:
                begin = i
            
            cur_need[k] = cur_need.get(k, {"cnt" : 0, "pos" : []})
            if cur_need[k]["cnt"] < need[k]:
                cur_need[k]["cnt"] = cur_need[k]["cnt"] + 1
                cur_need[k]["pos"].append(i)
                length += 1
            else:
                cur_need[k]["pos"].append(i)
                cur_need[k]["pos"].pop(0)
                l = []
                for key in cur_need:
                    l.append(cur_need[key]["pos"][0])
                begin = min(l)
                
            if length == len(t) and (ret == "" or i + 1 - begin < len(ret)):
                ret = s[begin : i + 1]
        
        return ret

# 滑动窗口,窗口左边界i,有边界j.  
# 1. 右界j不断右滑直到窗口内"包含了所有t的字母" 
# 2.此时左边界i右滑,将不必要的元素剔除,直到碰到一个"必须包含"的元素,此时窗口长度为最小,找到一个解.  
# 3. 左界i+1, 此时不满足条件,右界继续右移,重新按照步骤1寻找解.
class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        need = collections.defaultdict(int)
        for k in t:
            need[k] += 1
            
        l, r = 0, 0        
        while l < len(s):
            k = s[l]
            if k in need:
                break
            l += 1
        
        r = l
        windows = collections.defaultdict(int)
        length = 0
        ret = ""
        
        while r < len(s):
            k = s[r]
            r += 1
            if not k in need:
                continue
            
            windows[k] += 1
            if windows[k] <= need[k]:
                length += 1
            else:
                while l < r:
                    k = s[l]
                    if not k in need:
                        l += 1
                        continue
                    if windows[k] - 1 < need[k]:
                        break
                    windows[k] -= 1
                    l += 1
                    
            if length == len(t) and ret == "" or len(ret) > r - l:
                ret = s[l : r]
            
            if len(ret) == len(t):
                return ret
        
        return ret

t = Solution()
print(t.minWindow("ADOBECODEBANC", "ABC"))
# print(t.minWindow("ab", "b"))